﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics.Contracts;

namespace DataStructure.Interview
{
    public class Question85
    {
        public static int Fibo(int n)
        {
            // argu check
            if (n < 0) return -1;
            else if (n == 0) return 0;
            else if (n == 1) return 1;

            return Fibo(n - 1) + Fibo(n - 2);
        }

       public static int fibo(int n)
        {
            if (n < 0) return -1; // Error condition.
            if (n == 0) return 0;
            int a = 1, b = 1;
            for (int i = 3; i <= n; i++)
            {
                int c = a + b;
                a = b;
                b = c;
            }
            return b;
        }
        public static int FiboInloop(int n)
        {
            if (n < 0) return -1;
            else if (n == 0) return 0;
            else if (n == 1) return 1;

            int n0 = 0;
            int n1 = 1;
            int n2 = 0;

            for (int i = 2; i <= n; i++)
            {
                n2 = n0 + n1;
                n0 = n1;
                n1 = n2;
            }
            return n2;
        }

    }
}
